import java.util.LinkedList;
import java.util.Queue;

public class MyStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }

    //模拟入栈：把元素放到不为空的队列中
    public void push(int x) {
        if (empty()) {
            //两个队列都为空时 默认放到qu1中
            qu1.offer(x);
        } else if (qu1.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }

    //将有元素的队列中的size-1个元素导入进空队列中
    //剩下的1个元素，就是要出栈的元素
    public int pop() {
        if (qu1.isEmpty()) {
            while (qu2.size() != 1) {
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }else {
            while (qu1.size() != 1) {
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        }
    }

    //将有元素的队列中的全部元素导入进空队列中
    //并用变量记录每一次导进的元素，最后一次导入的元素就是栈顶元素
    public int top() {
        int x = 0;
        if (qu1.isEmpty()) {
            while (!qu2.isEmpty()) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;
        }else {
            while (!qu1.isEmpty()) {
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        }
    }

    //当两个队列都为空时，说明栈为空
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}